package main

type TreeNode struct{
	Val int
	Left *TreeNode
	Right *TreeNode
}
/*
	给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
	需要将他们合并成一个新的二叉树，合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为NULL的节点将直接作为新二叉树的节点
*/
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode{
	if root1 == nil{
		return root2
	}
	if root2 == nil{
		return root1
	}
	//对树同时进行深度搜索
	newNode := dfs(root1,root2)
	return newNode
}

func dfs(root1 *TreeNode, root2 *TreeNode) *TreeNode{
	//判断当前节点是否为空
	if root1 == nil{
		return root2
	}
	if root2 == nil{
		return root1
	}
	//两者皆不为空
	newNode := &TreeNode{0,nil,nil}
	newNode.Val = root1.Val+root2.Val
	//左节点
	newNode.Left = dfs(root1.Left,root2.Left)
	//右节点
	newNode.Right = dfs(root1.Right,root2.Right)
	return newNode
}
